#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <stdexcept>
#include <cmath>

using namespace std;

/**
 * 220 滑动窗口 + 顺序查找表
 * 时间复杂度O(nlogn)
   空间复杂度O(k)
 **/
class Duplicate{
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
 		// 使用映射记录  
		set<long> record;	// 整型溢出
		// 滑动窗口长度固定 就是record长度,保证record 大小在k+1内
		for(int i = 0; i < nums.size();i++){
			// 当前窗口 添加新元素后是否出现满足题意数据对
			// 查找表查找是否存在当前要添加元素
			if(record.lower_bound((long)nums[i] - (long)t) != record.end() &&
				*record.lower_bound((long)nums[i] - (long)t) <= (long)nums[i] + (long)t){ // 存在该值
				return true;
			}
			// 否则新元素和滑动窗口任何数据都不重复
			record.insert[nums[i]];

			// 判断当前滑动窗口大小, 保证record中有k个元素
			if(record.size() == k + 1){
				record.erase(nums[i - k]);
			}
		}       
		return false;
    }

};
